#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-04-12 13:42:26


class Slot(object):

    def __init__(self, key=None, value=None):
        self.key, self.value = key, value


class HashTable(object):

    def __init__(self, initial_length=10):
        self.length = initial_length                        # 表的最大长度
        self._table = [Slot() for _ in range(self.length)]  # 存储元素的表
        self._count = 0                                     # 表中已有元素个数
        self._load_factor = 0.75                            # 载荷因子

    def _hash(self, key, probe=0):
        hash_value = (key + probe) % self.length
        slot = self._table[hash_value]
        if slot.key is not None and slot.key != key:
            probe += 1
            hash_value = self._hash(key, probe)
        return hash_value

    def _resize(self):
        self.length = self._count * 2  # 将表扩容到已有元素的两倍
        temp_table = self._table
        self._table = [Slot() for _ in range(self.length)]
        # 把原来已有的元素存入
        for item in temp_table:
            if(item.key is None):
                continue
            hash_value = self._hash(item.key, 0)
            self._table[hash_value] = item

    @property
    def _current_load(self):
        return self._count / self.length

    def add(self, key, value):
        # 如果比例大于载荷因子，则调整表长度
        if self._current_load > self._load_factor:
            self._resize()
        hash_value = self._hash(key, 0)
        slot = self._table[hash_value]
        slot.value = value
        if slot.key == key:  # Key 重复时只改变槽的值
            return
        slot.key = key
        self._count += 1

    def get(self, key, default=None):
        hash_value = self._hash(key, 0)
        slot = self._table[hash_value]
        return slot.value if slot.key == key else default

    def remove(self, key):
        hash_value = self._hash(key, 0)
        slot = self._table[hash_value]
        if slot.key is None:
            return
        slot.key = None
        slot.value = None
        self._count -= 1

    def __repr__(self):
        items = [
            "    {slot.key} -> {slot.value},".format(slot=slot)
            for slot in self._table if slot.key is not None
        ]
        items.insert(0, "{{\n  load: {}/{}, data:".format(self._count, self.length))
        items.append("}")
        return "\n".join(items)


if __name__ == "__main__":
    ht = HashTable(3)
    print(ht)
    ht.add(0, "0")
    ht.add(1, "a")
    print(ht)
    ht.add(2, "b")
    ht.add(3, "c")
    print(ht)
    ht.add(4, "d")
    print(ht)
    ht.remove(0)
    print(ht)
    print(ht.get(4))
